/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
/*
思路：把copy节点链接到原节链后面，然后再构建random节点，再拆分节点
算法流程：
1.复制各节点，构建新链表
2.构建新链表各节点的random指向
3.拆分还原新链表
*/
struct Node* copyRandomList(struct Node* head) {
    if(head == NULL) return NULL;
	//1.创建copy节点
    struct Node* cur = head;
    while(cur){
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        copy->next = cur->next;
        cur->next = copy;
        cur = cur->next->next;
    }
    //2.构建rondom
    cur = head;
    while(cur){
        if(cur->random == NULL){
            cur->next->random = NULL;
        }else{
            cur->next->random = cur->random->next;
        }
        cur = cur->next->next;
    }
    //3.拆分链表
    cur = head->next;
    struct Node* copyHead = head->next; 
    struct Node* prev = head;//记录原链表前驱结点
    struct Node* tail = head;//记录原链表后继节点
    while(cur->next != NULL){
        tail = prev->next->next;//记录原链表尾
        prev->next = tail;
        cur->next = tail->next;
        //迭代
        prev = prev->next;
        cur = cur->next;
    }
    prev->next = NULL;
    return copyHead; 
}